#include "DynamicArray1.h"
#include <iostream>

DynamicArray1::DynamicArray1(void(*free)(ElementType)):size(0),capacity(15)
{
    a = new ElementType[this->capacity];
    this->free = free;
    this->Compare = nullptr;//???为什么初始化是空呢
}

DynamicArray1::~DynamicArray1()
{
    if(free != nullptr)
    {
        for(int i = 0; i < size; i++)
            this->free(a[i]);
    }
    delete []a;
}

DynamicArray1::DynamicArray1(const DynamicArray1 &d)
{
    this->size = d.size;
    this->capacity = d.capacity;
    this->a = new ElementType[this->capacity];
    for(int i = 0; i < this->size; i++)
    {
        a[i] = d.a[i];
    }
}

DynamicArray1 &DynamicArray1::operator=(const DynamicArray1 &d)
{
    delete []a;
    this->size = d.size;
    this->capacity = d.capacity;
    this->a = new ElementType[this->capacity];
    for(int i = 0; i < this->size; i++)
    {
        a[i] = d.a[i];
    }
    return *this;
}

void DynamicArray1::show(void (*func)(ElementType))
{
    for(int i = 0; i < size; i++)
    {
        func(a[i]);
    }
}

void DynamicArray1::Resize(int newCapacity)
{
    //允许往小了扩
    this->size = size > newCapacity ? newCapacity : size;
    this->capacity = newCapacity;
    ElementType *newP = new ElementType[newCapacity];
    for(int i = 0; i < size; i++)
    {
        newP[i] = a[i];
    }
    delete []a;
    a = newP;
}

void DynamicArray1::InsertTail(ElementType element)
{
    if(size >= capacity)
        Resize(capacity * 2);//扩容两倍
    
    this->a[size++] = element;

}

void DynamicArray1::InsertHead(ElementType element)
{
    if(size >= capacity)
        Resize(capacity * 2);
    for(int i = this->size; i >= 1; i--)
    {
        a[i] = a[i - 1];
    }
    a[0] = element;
    size++;
}

void DynamicArray1::InsertByIndex(ElementType element, int index)
{
    if(index < 0 || index > size)
    {
        std::cout<<"invalid index"<<std::endl;
        return;//非法插入直接return
    }
    if(size >= capacity)
        Resize(capacity * 2);
    for(int i = size; i > index; i--)
    {
        a[i] = a[i - 1];
    }
    a[index] = element;
    size++;
}

void DynamicArray1::RemoveByIndex(int index)
{
    for(int i = index; i < size - 1; i++)
    {
        a[i] = a[i + 1];
    }
    size--;
}

// void DynamicArray1::RemoveByElement(ElementType element)//!!
// {
//     for(int i = 0; i < size; i++)
//     {
//         if(a[i] == element)
//         {
//             RemoveByIndex(i);
//             i--;
//         }
//     }
// }
void DynamicArray1::RemoveByElement(ElementType element,bool(*isEqual)(ElementType,ElementType))//!!
{
    for(int i = 0; i < size; i++)
    {
        if(isEqual(a[i],element))
        {
            this->free(a[i]);
            RemoveByIndex(i);
            i--;
        }
    }
}

void DynamicArray1::UpDateByIndex(int index, ElementType newElement)
{
    if(index < 0 || index > size)
    {
        std::cout<<"invalid index"<<std::endl;
        return;//非法插入直接return
    }
    a[index] = newElement;

}

void DynamicArray1::UpDateByElement(ElementType oldValue, ElementType newValue)
{
    for(int i = 0; i < size; i++)
    {
        if(a[i] == oldValue)
            a[i] = newValue;
    }
}

ElementType &DynamicArray1::operator[](int index)
{
    return a[index];
}

DynamicArray1 DynamicArray1::FindByElement(ElementType element)
{
    DynamicArray1 result(nullptr);
    for(int i = 0; i < size; i++)

    {
        if(a[i] == element)
        {
            result.InsertTail((void*)i);//int强转为void*
        }
    }
    return result;
}

void DynamicArray1::SetSortCallBack(bool (*Compare)(ElementType, ElementType))
{
    this->Compare = Compare;//设置比较器函数
}

void DynamicArray1::Sort()
{
    if(Compare == nullptr)
    {
        std::cout<<"排序比较器为空！\n";
        return;
    }
    Sort(0,size - 1);
}

//二分查找
int DynamicArray1::BinarySearch(ElementType element)
{
    Sort();//先排序
    int left = 0;
    int right = size - 1;
    while(left <= right)//没相遇就继续找
    {
        int mid = (left & right) + ((left ^ right)>> 1);//找中间点，防止数据溢出！！不能写(left+right)/2
        if(a[mid] == element)//就是我要找的值
            return mid;
        else if(a[mid] > element)//去找左边
            right = mid - 1;//画图理解
        else if(a[mid] < element)//去找右边
            left = mid + 1;
    }
    return -1;//找不到返回-1，代表数是错的
}

void DynamicArray1::Deduplicate()
{
    Sort();
    for(int i = 1; i < size; i++)//因为跟前面的数相比，所以从1开始
    {
        if(a[i] == a[i - 1])//只需要和前一个比较，如果相等则按位置删除
        {
            RemoveByIndex(i--);//调用按位置删除
        }
    }
}

//归并排序：合并已经有序的两个数列
DynamicArray1 DynamicArray1::Merge(const DynamicArray1 &d)//返回值也是数组
{
    DynamicArray1 result(nullptr);//传nullptr的原因：？？？
    int i = 0, j = 0;//双指针
    while(i < this->size && j < d.size)//都没有到尾巴则继续
    {
        if(a[i] < d.a[j])//谁小则插入谁
            result.InsertTail(a[i++]);//尾插法
        else
            result.InsertTail(d.a[j++]);
    }

    while(i < this->size)//较长的数组尾部直接插入
        result.InsertTail(a[i++]);//继续插入当前数组

    while(j < d.size)
        result.InsertTail(d.a[j++]);//继续插入数组

    return result;
}

//快速排序
void DynamicArray1::Sort(int start, int end)
{
    if(start >= end)
        return;
    int left = start;
    int right = end;
    ElementType temp = a[left];
    while(left < right)
    {
        while(left < right && Compare(a[right], temp))//while(left < right && a[right] > temp)
            right--;
        if(left < right)
            a[left++] = a[right];
        while(left < right && Compare(temp, a[left]))//因为比较器是大于
            left++;
        if(left < right)
            a[right--] = a[left];
    }
    a[left] = temp;
    Sort(start,left - 1);
    Sort(right + 1,end);
}

std::ostream &operator<<(std::ostream &os, const DynamicArray1 &d)
{
    os<<"size:"<<d.size<<" capacity:"<<d.capacity<<std::endl;
    for(int i = 0; i < d.size;i++)
    {
        os<<d.a[i]<<" ";
    }
    os<<std::endl;
    return os;
}
